The present invention relates generally to asynchronous transfer mode (ATM) switching systems, and more particularly, to a method and system for dynamically allocating bandwidth to Available Bit Rate (ABR) virtual circuits in ATM switching systems.
In an ATM network, a virtual source (VS) transmits data in the form of fixed sized cells to a virtual destination (VD) through a connection (referred to as virtual circuit) established between the virtual source and the virtual destination. The virtual source and virtual destination may be a telephone, video equipment, facsimile, computer, edge-router, edge-switch, etc. The cells may include any type of digitized information, including audio, computer data, video, multimedia, Internet data, etc. For example, in a network that uses Transmission Control Protocol/Internet Protocol (TCP/IP) over ATM, a virtual source may be an edge-router at the entry to an ATM network. An entry edge-router segments the incoming TCP/IP data packets into one or more ATM cells before transmitting each cell to the ATM network. Similarly, a virtual destination may be an edge router at the exit of the ATM network. An exit edge-router reassembles incoming ATM cells into TCP/IP data packets before transmitting each packet to its destination.
When establishing a virtual circuit through an ATM network, a virtual source can select one of five different categories of service: Constant Bit rate (CBR), Variable Bit Ratexe2x80x94Real Time (VBR-RT), Variable Bit Ratexe2x80x94Non Real Time (VBR-NRT), Available Bit Rate (ABR), and Unspecified Bit Rate (UBR). ATM Forum Traffic Management Standard af-tm-0056.00 describes each of these services.
The ABR service determines excess bandwidth in the network and uses network management methods to reallocate the excess bandwidth among the virtual circuits in the network to reduce network congestion and cell loss. In negotiating an ABR virtual circuit, a virtual source negotiates a peak cell rate (PCR) and a minimum cell rate (MCR) with the ATM network. PCR is the maximum cell rate a virtual circuit can support. MCR is the minimum cell rate that a virtual circuit must support. The ABR service uses the negotiated PCR and MCR parameters to provide a guaranteed quality of service concerning bandwidth availability and cell loss in a virtual circuit.
When a virtual source selects the ABR service, the virtual source periodically generates a resource management. (RM) cell to get feedback from the network on the rate at which the virtual source can transmit cells on a virtual circuit without causing loss of cells due to network congestion. Typically, a virtual source generates an RM cell for every thirty-one cells it transmits or at the expiration of a fixed time interval, whichever occurs first. The network processes the RM cell, updates virtual circuit bandwidth information in the RM cell, and returns the RM cell to the virtual source. The virtual source then dynamically adjusts its rate of cell transmission based on the bandwidth information contained in the RM cell.
An RM cell generated by a virtual source is referred to as a Forward RM cell. The Forward RM cell passes through one or more switching systems in the network before reaching a virtual destination. The virtual destination processes the Forward RM cell and returns a Backward RM cell to the virtual source. The Backward RM cell passes through one or more switching systems in the network before reaching the virtual source.
A virtual source maintains the MCR, current Allowed Cell Rate (ACR), and the PCR associated with the virtual circuit. ACR is the rate at which the network allows the virtual source to transmit cells on a virtual circuit. When a virtual source receives a Backward RM cell, based on the bandwidth information in the Backward RM cell, the virtual source computes a new ACR. Consequently, ACR dynamically changes as the network traffic changes and as the virtual source receives feedback from the network.
A Forward RM cell includes an MCR field, current cell rate (CCR) field, and an explicit rate (ER) field. CCR is the rate at which a virtual source is transmitting cells on a virtual circuit at the time the virtual source generates a Forward RM cell. ER is the rate at which the virtual source wishes to transmit cells on a virtual circuit. A virtual source cannot set the ER field in a Forward RM cell to be greater than PCR. After generating a Forward RM cell and setting the MCR, CCR, and ER fields in the Forward RM cell, the virtual source transmits the Forward RM cell to the network.
When a virtual source transmits a Forward RM cell, the Forward RM cell passes through each switching system on the path of the virtual circuit to the virtual destination. Each switching system on the path can either keep the ER in the Forward RM cell the same or decrease the ER to a lower rate. However, according to ATM Forum Traffic Management Standard, af-tm-0056.00, a switching system cannot decrease the ER below the MCR for the virtual circuit. Furthermore, a switching system cannot increase the ER for the virtual circuit. A switching system that allocates bandwidth to a virtual source by setting the ER field in an RM cell is referred to as an ABR Explicit Rate (ABR-ER) switching system.
When a Forward RM cell associated with a virtual circuit arrives at an ABR-ER switching system, the switching system determines an upper threshold (referred to as xe2x80x9ccutoffxe2x80x9d) for the bandwidth that can be made available to the virtual circuit in the switching system. If the switching system determines that the computed cutoff for the virtual circuit sets the ACR in the virtual source (i.e, the switching system computes the smallest cutoff among all of the switching systems on the path of the virtual circuit), then the switching system considers the virtual circuit to be xe2x80x9cbottlenecked herexe2x80x9d or bottlenecked in the switching system. If the switching system determines that the computed cutoff does not set the ACR in the virtual source (i.e, the switching system does not compute the smallest cutoff among all of the switching systems on the path of the virtual circuit), then the switching system identifies the virtual circuit as xe2x80x9cbottlenecked elsewhere.xe2x80x9d
The switching system determines a new bandwidth that it can allocate to the virtual circuit by determining a new ER for the virtual circuit and setting the new ER in the Forward RM cell. The switching system then determines an estimated rate (Exp_Rate) at which the switching system xe2x80x9cexpectsxe2x80x9d the virtual source to transmit data cells after the virtual source adjusts its ACR based on the newly set ER. Finally, the switching system sends the Forward RM cell to the next switching system on the path of the virtual circuit.
When the Forward RM cell reaches the virtual destination, the virtual destination returns the Forward RM cell as a Backward RM cell. The Backward RM cell passes through one or more switching systems on the path of the virtual circuit without any further modification to the bandwidth information set in the Forward RM cell. When the Backward RM cell reaches the virtual source, the virtual source uses the new ER in the RM cell to determine a new ACR. Based on the new ACR, the virtual source adjusts the rate at which it transmits cells.
Every time a switching system determines a cutoff and ER for a virtual circuit, the switching system also recomputes certain global bandwidth parameters for the virtual circuits that the switching system handles. These global bandwidth parameters include the total bandwidth available to all ABR-ER virtual circuits, the total Exp_Rate for ABR-ER virtual circuits that are bottlenecked elsewhere, the total number of ABR-ER virtual circuits that are bottlenecked elsewhere, and the total number of ABR-ER virtual circuits that are bottlenecked at the switching system.
Methods for determining and updating the global bandwidth parameters in an ABR-ER switching system are known. However, these methods have the disadvantage that every time a switching system recomputes the global bandwidth parameters that the switching system maintains on its virtual circuits, the computations introduce errors in the form of round-off errors into the global bandwidth parameters. Over the life of the vial circuits, as the switching system recomputes the global bandwidth parameters, the round-off errors can accumulate, and as a result of the accumulated errors, the parameters gradually become inaccurate.
When an ABR-ER switching system maintains inaccurate global bandwidth parameters, the switching system fails to allocate an optimum bandwidth to each virtual circuit. Specifically, a switching system allocates an optimum bandwidth to a virtual circuit when the virtual source uses the entire or nearly the entire bandwidth allocated to the virtual circuit. If the global bandwidth parameters are inaccurate, the switching system may allocate an insufficient amount of bandwidth to a virtual circuit, even though the switching system may in fact have sufficient bandwidth available. Similarly, the switching system may allocate an excessive amount of bandwidth to a virtual circuit, even though the switching system may in fact have insufficient bandwidth available. In either case, the switching system would fail to allocate an optimum bandwidth to the virtual circuit.
The methods known prior to the present invention for determining and updating the global bandwidth parameters in an ABR-ER switching system have the additional disadvantage that, when a virtual circuit does not use the entire bandwidth a switching system allocates to it, the switching system cannot dynamically identify and reallocate the unused bandwidth to other virtual circuits in the switching system. For example, when a virtual source stops transmitting cells on a virtual circuit or transmits cells at a much lower rate than the bandwidth allocated to the virtual circuit permits, the virtual source does not use the bandwidth allocated to the virtual circuit in an optimum fashion.
Furthermore, the methods known prior to the present invention for allocating bandwidth to an ABR virtual circuit have the disadvantage that a switching system may allocate more bandwidth to the virtual circuit than a virtual source could use. For example, when a virtual source requests an ER that is below the MCR for a virtual circuit, the switching system cannot decrease the ER below the MCR.
Therefore, it is desirable to have a method and system for overcoming the disadvantages of the prior art. It is also desirable to have a method and system to efficiently and effectively increase the total bandwidth that a switching system can make available to virtual circuits. It is further desirable to have a method and system for correcting, within a fixed time interval, the accumulation of computational errors in the global bandwidth parameters maintained in an ABR-ER switching system, identifying the unused bandwidth in virtual circuits, allocating the identified unused bandwidth to other virtual circuits in the switching system, and increasing the total bandwidth that the switching system can make available to virtual circuits.
The present invention comprises a method and system for dynamically adjusting the total bandwidth that an ABR-ER switching system can make available to ABR virtual circuits in the switching system by recomputing, at fixed time intervals, the total bandwidth that the switching system can make available to active ABR virtual circuits that are bottlenecked in the switching system. The method and system classifies the ABR virtual circuits that are established through an output port of the switching system into three categories of xe2x80x9crecently active,xe2x80x9d xe2x80x9cactive,xe2x80x9d and xe2x80x9cinactivexe2x80x9d virtual circuits. An ABR virtual circuit is xe2x80x9crecently activexe2x80x9d if an output port receives at least one RM cell for the virtual circuit since the most recent recomputation of the total bandwidth that the switching system can make available to active ABR virtual circuits that are bottlenecked in the switching system (hereinafter referred to as xe2x80x9cbandwidth allocation updatexe2x80x9d). An ABR virtual circuit is xe2x80x9cactivexe2x80x9d if an output port receives at least one RM cell within the two most recent bandwidth allocation updates. An ABR virtual circuit is xe2x80x9cinactivexe2x80x9d if an output port does not receive at least one RM cell within the two most recent bandwidth allocation updates.
The present invention further comprises a method and system for dynamically adjusting the total bandwidth that an ABR-ER switching system can make available to ABR virtual circuits in the switching system by determining a set of weighted xe2x80x9ccutoffsxe2x80x9d for the ABR virtual circuits, respectively, determining a first total expected rate (Exp_Rate) for recently active virtual circuits that are bottlenecked elsewhere based on the weighted cutoffs, setting a second total expected rate for active virtual circuits that are bottlenecked elsewhere to the first total expected rate, determining a total bandwidth available in the switching system for active virtual circuits that are bottlenecked in the switching system based on the first total expected rate, and setting to zero the first total expected rate.
A switching system consistent with the present invention determines the total bandwidth allocated to inactive ABR virtual circuits in the switching system without explicitly identifying the inactive ABR virtual circuits, and makes available the bandwidth allocated to inactive ABR virtual circuits to active ABR virtual circuits that are established through the switching system. When transmission of cells resumes in an inactive ABR virtual circuit, the switching system reallocates new bandwidth to the virtual circuit.
The description of the invention and the following description for carrying out the best mode of the invention should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. The accompanying drawings, which form part of the description for carrying out the best mode of the invention, show several embodiments of the invention, and together with the description, explain the principles of the invention.